Échantillonnage

L’estimation de la taille des vues nécessite souvent que l’on puisse sélectionner rapidement et en utilisant peu de mémoire un échantillon dans un grand ensemble de données.

On distingue conceptuellement deux types d’échantillon. Dans le premier cas, on attribue à chaque données une certaine probabilité d’être sélectionnée. Par exemple, on voudra un échantillon où chaque élément est sélectionné avec une probabilité de 1 sur 10. Dans le second cas, on détermine a priori la taille de l’échantillon. Par exemple, on voudra sélectionner 10 éléments peu importe la taille de l’ensemble. Nous nous intéresserons ici à ce second cas.

Idéalement, on souhaite sélectionner rapidement l’échantillon. Comme l’échantillon est souvent beaucoup plus petit que l’ensemble initial, on souhaite que le temps de calcul soit proportionnel à la taille de l’échantillon et non pas à la taille de l’ensemble initial.

Il faut tenir compte du fait qu’on ne connaît pas toujours la taille de notre ensemble de données ! Prenons un exemple concret. Supposons qu’on cherche à construire un échantillon du résultat de cette requête :

Pour déterminer la taille de cette requête, il faudra d’abord visiter toutes les rangées de notre table [1], déterminer la valeur $ n$, puis ensuite sélectionner notre échantillon. Voilà qui est inefficace puisqu’il faut visiter chaque rangée deux fois !

Il existe une approche efficace qui permet de ne visiter chaque élément de donnée qu’une seule fois. La technique en question est appelée reservoir sampling en anglais [2]. Le « réservoir » $ R$ est un tableau de taille $ N$.

– On stocke les premiers $ N$ éléments rencontrés dans $ R$
– On visite ensuite les éléments aux positions $ k=N+1, N+2,\ldots, n$ un par un. Avec une probabilité $ N/k$, on remplace un élément choisi aléatoirement dans le réservoir par le nouvel élément.

Avec cet algorithme simple, on est certain d’avoir un échantillonnage aléatoire, en ne visitant chaque valeur qu’une seule fois. Par contre, cette approche génère un nombre aléatoire pour chaque donnée, ce qui peut être coûteux. La complexité algorithmique est d’au moins $ O(n)$ puisqu’il faut visiter chaque élément au moins une fois. Nous n’avons donc pas atteint notre objectif d’avoir un temps de calcul qui ne dépend que de la taille de l’échantillon.

Remarque. Le nombre attendu d’éléments retenus avec une probabilité $ N/k$ dans l’algorithme reservoir sampling est $ \sum_{k=N+1}^n N/k\approx n \log n/N$.

Heureusement, on peut faire encore mieux [3]. Bien qu’il ne soit pas possible d’atteindre une complexité $ O(N)$, on peut réduire la complexité à $ O(N(1+\log(n/N))$. L’astuce consiste à passer par-dessus un nombre aléatoire d’éléments (qu’on ne consulte même pas) à chaque itération. Malheureusement, cet algorithme est plus difficile à décrire et à implémenter parce qu’il fait appel à des distributions aléatoires non uniformes. (Dans ce cours, je ne vais pas vous demander de mettre en pratique cet algorithme, mais vous devez tout de même en comprendre l’idée essentielle.)

Voici tout de même un aperçu de l’algorithme en question :

– On stocke les premiers $ N$ éléments rencontrés dans $ R$.
– On pose $ k\leftarrowN$
– Tant qu’on n’a pas atteint la fin du fichier :

• On passe par dessus $ S(N,t)$ éléments : $ k\leftarrow k+1 +S(N,t)$ ($ S(N,t)$ est une variable aléatoire).
• On remplace un élément choisi aléatoirement dans le réservoir par le nouvel élément à la position $ k$ dans le fichier.

Selon Vitter, la variable aléatoire $ S(N,t)$ doit être telle que
$ P(S(N,t)\leq s)=1-\frac{t^{\underline{N}}}{(t+s+1)^{\underline{N}}}$ où l’on utilise la convention selon laquelle $ a^{\underline{b}}=a !/(a-b) !$. (L’analyse et le calcul de cette variable aléatoire dépassent le cadre du présent cours.)

En SQL ?

Les bases de données relationnelles Oracle supportent l’échantillonnage directement en SQL :

Malheureusement, tel n’est pas le cas de toutes les bases de données.

Le professeur Alan Dix a écrit une page dans laquelle il présente différentes stratégies pour construire des échantillons en SQL.

En supposant que votre table initiale (appelée « table ») dispose d’une clé primaire appelée key, voici comment faire un échantillonnage de 100 rangées selon la méthode décrite par Alan Dix :

(On suppose que les tables data_rnd and selection ont été créées précédemment. Il est possible d’obtenir le même résultat en faisant moins de 3 requêtes SQL.)

Malheureusement, cette stratégie est relativement inefficace : elle génère un nombre aléatoire pour chaque rangées de notre base données ! La mise en oeuvre d’une méthode efficace d’échantillonnage dans une base de données particulière peut donc nécessiter un peu de travail.

En résumé

– En théorie, il est possible de prendre un échantillon aléatoire de taille $ N$ à partir d’un ensemble contenant $ n$ élément dans un temps $ O(N (1+ \log (n/N))$.
– En pratique, la plupart des algorithmes requièrent un temps $ O(n)$ puisqu’ils génèrent un nombre aléatoire par élément de l’ensemble. En somme, leur temps de calcul dépend de la taille totale de la table, et non seulement de la taille de l’échantillon.
– En SQL, on peut devoir travailler un peu afin de mettre en oeuvre un échantillonnage efficace, à moins d’utiliser une base de données Oracle ou un autre système qui prévoit l’échantillonnage.

Pour en savoir plus...

– Olken, F. et Rotem, D., Simple Random Sampling from Relational Databases, VLDB’86, pages 160-169, 1986.